package www.study.com;

//缺失的第一个正数 https://leetcode.cn/problems/first-missing-positive/
//参见《左程云代码面试指南》
public class code41 {
    public static void main(String[] args) {

    }

    class Solution {
        public int firstMissingPositive(int[] nums) {
            int l = 0; //遍历到当前位置为止，已经包含的正整数范围为[1,l]，也代表当前遍历到的下标位置
            int r = nums.length; //期望最优的情况下，可能包含的正整数范围为[1,r]
            while(l < r){
                if(nums[l] == l + 1){
                    l++;
                }else if(nums[l] <= l || nums[l] > r || nums[nums[l] - 1] == nums[l]){
                    swap(nums,l,--r);
                }else{
                    swap(nums,nums[l] - 1,l);
                }
            }
            return l + 1;
        }
        public void swap(int[] nums,int a,int b){
            int tmp = nums[a];
            nums[a] = nums[b];
            nums[b] = tmp;
        }
    }
}
